package _go

/*n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。



示例 1：


输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：

输入：n = 1
输出：[["Q"]]
*/
//主要思路 需要用几个set记录皇后的存放位置和攻击范围
//存放位置一个一维数组就可以表示存放位置 数组下标表示行数 数值表示列
//主要的难点在左斜线和右斜线的的攻击范围 用两个函数表示 已经被攻击的格子  有 y + x  =c  和 y-x =c
//这样就表示被攻击的格子了
//剩下就是回溯的过程 注意的是 不仅要回溯被攻击的格子 还是回溯q的站位

//申请一个全局变量
var res [][]string

func solveNQueens(n int) [][]string {

	//初始化结构体
	res = [][]string{}

	//申请一个存放放q的数据 下表标识行数  value标识列数
	queues := make([]int, n)
	//初始化一下
	for k, _ := range queues {
		queues[k] = -1
	}

	//初始化 lie l r两个撇的set 更好的是用布尔型
	lie, rXie, lXie := map[int]int{}, map[int]int{}, map[int]int{}
	//递归调用
	findQ(queues, 0, n, lie, lXie, rXie)
	return res
}

//参数定义
//queue的放的位置
//hang:当前行数
// n:n个皇后
//lie:lie的占用情况
//xie:xie的占用情况
func findQ(queues []int, hang, n int, lie, lXie, rXie map[int]int) {
	//跟正常的递归一样 先写结束条件
	if hang == n {
		//所有的都放完了  把结果写入结果集
		resTmp := fmtQueue(queues, n)
		res = append(res, resTmp)
		return
	}
	for i := 0; i < n; i++ {
		rXieKey := (i + hang)
		lXieKey := (i - hang)
		if rXie[rXieKey] == 1 || lXie[lXieKey] == 1 || lie[i] == 1 {
			continue
		}
		//写入结果
		queues[hang], rXie[rXieKey], lXie[lXieKey], lie[i] = i, 1, 1, 1
		//处理下一个行
		findQ(queues, hang+1, n, lie, lXie, rXie)
		//回溯
		queues[hang], rXie[rXieKey], lXie[lXieKey], lie[i] = -1, 0, 0, 0

	}
}

//格式化输出
func fmtQueue(queues []int, n int) (res []string) {
	for i := 0; i < n; i++ {
		row := make([]byte, n)
		for j := 0; j < n; j++ {
			row[j] = '.'
		}
		row[queues[i]] = 'Q'
		res = append(res, string(row))
	}
	return res
}
